/* 键为插入序号的平方探测法：
 * 首先把元素排好序号
 * 然后依次按照哈希函数插入哈希值位置中
 * 若出现冲突（ACTIVE），则应用平方探测
*/
#include<array>
#include<vector>
template <typename HashedObj>
class HashTable
{
public:
    /* 常量枚举：
     * ACTIVE表示该位置已被占据
     * EMPTY表示未被占据
     * DELETE表示该项已主动删除
    */
    enum EntryType{ ACTIVE, EMPTY, DELETED };
private:
    /*含有序号的键值对对象Obj*/
    struct HashEntry
    {
        HashedObj element;
        /*存储序号的枚举*/
        EntryType info;

        /*初始时，序号i默认为EMPTY*/
        HashEntry( const HashedObj & e = HashedObj {}, HashEntry i = EMPTY) : element{e}, info{i} {}
        HashEntry( HashedObj && e, HashEntry i = EMPTY ) : element{std::move(e)} , info{i} {}
    };
    /*存储Obj的向量*/
    vector<HashEntry> array;
    /*哈希表Obj个数*/
    int currentSize;

    /*检测序号i是否为ACTIVE*/
    bool isActive(int currentPos) const
        { return array[currentPos].info == ACTIVE; }
    /*根据键值对对象（Obj）查找键（序号）*/
    int findPos(const HashedObj & x) const
    {
        int offset = 1;             //探测的次数
        int currentPos = myHash(x); //当前位于的哈希值

        /*利用平方消解函数，循环至 找到空位置或找到x*/
        while (array[currentPos].info != EMPTY && array[currentPos].element != x)
        {
            /*平方消解函数*/
            currentPos += offset;
            offset += 2;
            // 若超出向量大小，则进行同余转换
            if(currentPos >= array.size())
                currentPos -= array.size();
        }
        return currentPos;
    }
    /*重建函数（再散列）*/
    void rehash()
    {   
        /*保存原哈希表*/
        vector<HashEntry> oldArray = array;
        /*建立新哈希表*/
        array.resize( nextPrime(2 * oldArray.size()) );
        /*清空原哈希表*/
        for (auto & entry : array)
            entry.info = EMPTY;
        /*对新哈希表赋值*/
        currentSize = 0;
        for (auto & entry : oldArray)
            if(entry.inf == ACTIVE)
                insert (std::move(entry.element));
    }
    /*哈希函数*/
    size_t myHash(const HashedObj & x) const

public:
    /*哈希表默认是素数长度*/
    explicit HashTable( int size = 101 ) : array(nextPrime(size))
    /*清空函数（依赖序号）*/
    void makeEmpty()
    {
        currentSize = 0;
        /*把序号*/
        for (auto & entry : array)
            entry.info = EMPTY;
    }
    /*查找函数（依赖序号）*/
    bool contains(const HashedObj & x) const
        { return isActive(findPos(x)); }
    /*插入函数*/
    bool insert(const HashedObj & x)
    {
        int currentPos = findPos(x);
        if ( isActive(currentPos) )
            return false;
        /*进行插入赋值*/
        array[ currentPos ].element = x;
        array[ currentPos ].info = ACTIVE;
        /*装填因子超过0.5，则认为其是满的（已证明素数长度的哈希表未半满时总可以插入新值），此时需要重建哈希表*/
        if(++currentSize > array.size() / 2)
            rehash();
        return true; //插入成功
    }
    bool insert(HashedObj && x)
    /*删除项*/
    bool remove(const HashedObj & x)
    {
        int currentPos = findPos(x);
        if (!isActive(currentPos))
            return false;
        
        array[currentPos].info = DELETE;
        return true;
    }
    
};